public class Repetition_BinarySearchTree {
    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        if(root==null){
            root=new TreeNode(key);
        }
        TreeNode t=root;
        TreeNode tp=null;
        while(t!=null){
            if(key>t.key){
                tp=t;
                t=t.right;
                if(t==null) tp.right=new TreeNode(key);
            }else {
                if (key<t.key){
                    tp=t;
                    t=t.left;
                    if(t==null) tp.left=new TreeNode(key);
                }else return false;
            }
        }
        return true;
    }
    //查找key是否存在
    public TreeNode search(int key) {
        if (root==null) return null;
        TreeNode t= root;
        while(t!=null){
            if(t.key==key) return t;
            if(key>t.key){
                t=t.right;
            }else t=t.left;
        }
        return null;
    }
    //删除key的值
    public boolean remove(int key) {
        boolean jud=false;
        if(root==null) return true;
        TreeNode cur = root;
        TreeNode parent =null;
        while(cur!=null){
            if(cur.key>key){
                parent=cur;
                cur=cur.left;
            }else {
                if(cur.key<key){
                    parent=cur;
                    cur=cur.right;
                }else{
                    jud=removeNode(cur,parent);
                    break;
                }
            }
        }
        return jud;
    }

    private boolean removeNode(TreeNode cur,TreeNode parent){
        boolean remove = false;
        if(cur.left==null){
            if(cur==root){
                root=root.right;
            }else{
                if(cur==parent.left){
                    parent.left=cur.right;
                }else{
                    parent.right=cur.right;
                }
            }
            remove=true;
        }else {
            if(cur.right==null){
                if(cur==root){
                    root=root.left;
                }else{
                    if (cur==parent.left){
                        parent.left=cur.left;
                    }else{
                        parent.right=cur.left;
                    }
                }
                remove=true;
            }else{
                    TreeNode cp=cur;//cur在cp的左边；
                    parent=cur;
                    cur=cur.right;
                    while(cur.left!=null){
                        cp=cur;
                        cur=cur.left;
                    }
                parent.key=cur.key;
                    if(cp.left==cur){
                        cp.left=cur.right;
                    }else {
                        cp.right=cur.right;
                    }
                    remove=true;
                }
            }

        return remove;
    }
}
